跳到主要内容

Simon 算法

阐述​

Simon 问题​

给定一个 f:Σn→Σnf:\Sigma^n\to\Sigma^n，它是二对一的且存在一个 c∈Σnc\in\Sigma^n，使得 f(x)=f(x⊕c)f(x)=f(x\oplus c)。找出 cc。

Simon 算法​

构造一个黑箱 OfO_f 使得

Of∣x⟩∣z⟩=∣x⟩∣z⊕f(x)⟩O_{f}|x\rangle|z\rangle=|x\rangle|z \oplus f(x)\rangle

准备两组长度为 nn 的寄存器，依次作用 H⊗nH^{\otimes n}、OfO_f 和 H⊗nH^{\otimes n}，然后测量第一组寄存器。此时系统状态为

∑k=02n−1(12n∑j=02n−1(−1)j⋅k∣f(j)⟩)∣k⟩\sum_{k=0}^{2^{n}-1}\left(\frac{1}{2^{n}}\sum_{j=0}^{2^{n}-1}(-1)^{j \cdot k}|f(j)\rangle\right)|k\rangle

括号内的振幅不为 0 当且仅当 c⋅k=0c\cdot k=0，因此测量得到的结果满足这一条件。由于共有 2n−12^{n-1} 个正交向量，进行 n−1n-1 次测量中，第 ii 次取得的向量与此前的线性相关的概率是 2i−n2^{i-n}，所以每次找到合适的向量的期望次数小于 2。总体运算时间 O(n2)O(n^2)。

Simon 算法是一个量子反作用的例子。

实例​

性质​

相关内容​

参考文献​